// 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
// 根节点的引用。
//
// 一般来说，删除节点可分为两个步骤：
//
// 首先找到需要删除的节点；
// 如果找到了，删除它。
//
// 示例 1:
//
// 输入：root = [5,3,6,2,4,null,7], key = 3
// 输出：[5,4,6,2,null,null,7]
// 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
// 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
// 另一个正确答案是 [5,2,6,null,4,null,7]。
//
// 示例 2:
//
// 输入: root = [5,3,6,2,4,null,7], key = 0
// 输出: [5,3,6,2,4,null,7]
// 解释: 二叉树不包含值为 0 的节点
//
// 示例 3:
//
// 输入: root = [], key = 0
// 输出: []
//
// 提示:
//
// 节点数的范围 [0, 10⁴].
// -10⁵ <= Node.val <= 10⁵
// 节点值唯一
// root 是合法的二叉搜索树
// -10⁵ <= key <= 10⁵
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
//
// Related Topics 树 二叉搜索树 二叉树 👍 1122 👎 0
package main

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

//type TreeNode struct {
//	Val   int
//	Left  *TreeNode
//	Right *TreeNode
//}

func deleteNode(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return root
	}

	if root.Val == val {
		if root.Left == nil && root.Right == nil {
			return nil
		} else if root.Left == nil {
			return root.Right
		} else if root.Right == nil {
			return root.Left
		} else {
			successor := findMinNode(root.Right)
			successor_copy := &TreeNode{Val: successor.Val}
			successor_copy.Left = root.Left
			successor_copy.Right = removeMinNode(root.Right)
			return successor_copy
		}
	} else if val > root.Val {
		root.Right = deleteNode(root.Right, val)
		return root
	} else {
		root.Left = deleteNode(root.Left, val)
		return root
	}
}

func findMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	for root.Left != nil {
		root = root.Left
	}

	return root
}

/*
*
root分为三种情况
root==nil: 直接返回	(实际不可能，因为只有左右节点都存在时才会走到该方法)
root左节点存在: 深入左子树找最小节点，且返回最小节点
root左节点不存在: 那么最小节点就是root，直接返回root.Right
*/
func removeMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}

	if root.Left != nil {
		root.Left = removeMinNode(root.Left)
		return root
	} else {
		tmp := root.Right
		root.Right = nil
		return tmp
	}
}

//leetcode submit region end(Prohibit modification and deletion)
